package org.ymx.myTree;

/**
 * 二叉查找树
 */

/**
 * Comparable此接口强行对实现它的每个类的对象进行整体排序。
 * 类的 compareTo 方法被称为它的自然比较方法。
 * 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。
 *
 * @param <AnyType>
 */
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {

    private BinaryNode<AnyType> root;

    public BinarySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    //contains  包含;容纳
    public boolean contains(AnyType x) {
        return contains(x, root);
    }

    public AnyType findMin() {
        if (isEmpty()) throw new NullPointerException();
        return findMin(root).element;
    }

    public AnyType findMax() {
        if (isEmpty()) throw new NullPointerException();
        return findMax(root).element;
    }

    public void insert(AnyType x) {
        root = insert(x, root);
    }

    public void remove(AnyType x) {
        root = remove(x, root);
    }

    public void printTree(String model) {
        printTree(root, model);
    }

    /**
     * 四种基本的遍历思想为：
     * <p>
     * 前序遍历：根结点 ---> 左子树 ---> 右子树 = prev
     * 中序遍历：左子树---> 根结点 ---> 右子树 = mid  有序的
     * 后序遍历：左子树 ---> 右子树 ---> 根结点 = next
     * 层次遍历：从上到下，从左到右。
     *
     * @param root
     */
    private void printTree(BinaryNode<AnyType> root, String model) {
        if (root == null) {
            //System.out.println("null");
            //一定要return
            return;
        }
        if ("prev".equals(model)) {
            System.out.println(root.element);
            printTree(root.left, model);
            printTree(root.right, model);
        } else if ("mid".equals(model)) {
            printTree(root.left, model);
            System.out.println(root.element);
            printTree(root.right, model);
        } else if ("next".equals(model)) {
            printTree(root.left, model);
            printTree(root.right, model);
            System.out.println(root.element);
        }
    }

    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return t;
        }
        int compare = x.compareTo(t.element);
        if (compare < 0) {
            t.left = remove(x, t.left);
        } else if (compare > 0) {
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) {
            t.element = findMax(t.right).element;
            t.right = remove(t.element, t.right);
        } else {
            t = (t.left != null) ? t.left : t.right;
        }
        return t;
    }


    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return new BinaryNode<>(x, null, null);
        }
        int compare = x.compareTo(t.element);
        if (compare < 0) {
            t.left = insert(x, t.left);
        } else if (compare > 0) {
            t.right = insert(x, t.right);
        } else {
            ;
        }
        return t;
    }


    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        if (t == null) {
            return null;
        } else if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
        if (t != null) {
            while (t.right != null) {
                t = t.right;
            }
        }
        return t;
    }


    /**
     * 判断该树是否含有x节点
     *
     * @param x
     * @param t
     * @return
     */
    private boolean contains(AnyType x, BinaryNode<AnyType> t) {
        if (x == null) {
            return false;
        }
        //比较x与t.element的大小
        int compare = x.compareTo(t.element);
        if (compare < 0) {
            return contains(x, t.left);
        } else if (compare > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }


    static class BinaryNode<AnyType> {
        //为了保证外部访问 private改成public或成为内部类
        private AnyType element;
        private BinaryNode<AnyType> left;
        private BinaryNode<AnyType> right;

        public BinaryNode(AnyType element, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }

        public BinaryNode(AnyType element) {
            this(element, null, null);
        }
    }
}


